package com.lz.tree;

import com.lz.tree.common.TreeNode;

import java.util.*;

/**
 * Tree翻转，路经，复杂的
 */
public class TreeReverse {
    public static void main(String[] args) {
        TreeReverse treeReverse = new TreeReverse();
//        treeReverse.invertTree()
    }

    /**
     * 简单翻转二叉树
     *
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        invertTree(root.left);
        invertTree(root.right);
        TreeNode treeNode = root.left;
        root.left = root.right;
        root.right = treeNode;
        return root;
    }

    /**
     * 翻转后二叉树是否相等
     *
     * @param root1
     * @param root2
     * @return
     */
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        if (root1.val != root2.val) return false;
        TreeNode left1 = root1.left;
        TreeNode left2 = root2.left;

        TreeNode right1 = root1.right;
        TreeNode right2 = root2.right;


        boolean flag = treeEuqal(left1, left2) && treeEuqal(right1, right2);
        if (!flag) {
            TreeNode tmp = left1;
            left1 = right1;
            right1 = tmp;

            flag = treeEuqal(left1, left2) && treeEuqal(right1, right2);
        }
        return flag && flipEquiv(left1, left2) && flipEquiv(right1, right2);

    }

    boolean treeEuqal(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) return true;
        if (node1 == null || node2 == null) return false;
        return node1.val == node2.val;
    }

    /**
     * 树最小深度
     *
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        int i = 0;
        if (root == null) return i;
        List<TreeNode> q = new LinkedList<TreeNode>();
        TreeNode cur = root;
        q.add(cur);
        while (q.size() > 0) {
            i++;
            int size = q.size();
            while (size > 0) {
                TreeNode temp = q.get(0);
                q.remove(0);
                if (temp.left != null) q.add(temp.left);
                else return i;
                if (temp.right != null) q.add(temp.right);
                else return i;

                size--;
            }
        }
        return i;
    }

    /**
     * 路径和等于指定树
     *
     * @param treeNode
     * @param sum
     * @return
     */

    boolean hasPathSum(TreeNode treeNode, int sum) {
        if (treeNode == null) return false;
        int sum1 = sum - treeNode.val;
        if (sum1 == 0 && treeNode.left == null && treeNode.right == null) return true;
        // 注意可以是负数
//        if (sum1 < 0) return false;
        return hasPathSum(treeNode.left, sum1) || hasPathSum(treeNode.right, sum1);
    }

    /**
     * 路径和等于指定数目，并返回节点信息
     *
     * @param treeNode
     * @param sum
     * @return
     */
    List<List<Integer>> list = new ArrayList<>();
    ArrayList<Integer> inner = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) return list;
        sum -= root.val;
        inner.add(root.val);  // 入列表
        if (root.left == null && root.right == null) {
            if (sum == 0) {
                list.add(new ArrayList<>(inner));  // 记得拷贝一份
            }

        }
        if (root.left != null) pathSum(root.left, sum);
        if (root.right != null) pathSum(root.right, sum);
        inner.remove(inner.size() - 1);  //从列表中删除
        return list;
    }

    public ArrayList<Integer> getInner() {
        return inner;
    }

    /**
     * 863. 二叉树中所有距离为 K 的结点
     * 没做出来，主要是父节点没有被记录。。。。
     * 解决方案将父节点保存在一个map中
     *
     * @param root
     * @param target
     * @param K
     * @return
     */

    List<Integer> distance = new ArrayList<>();

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        // 遍历确定target节点
        DFSRc(root);
        int treeNode = doEqual(root, target);
        doDistanceK(treeNode, K);
        return distance;
    }


    List<TreeNode> res0 = new LinkedList<>();
    Set<Integer> fonf = new HashSet<>();

    void DFSRc(TreeNode treeNode) {
        if (treeNode == null) return;
        res0.add(treeNode);
        DFSRc(treeNode.left);
        DFSRc(treeNode.right);

    }

    int doEqual(TreeNode root, TreeNode target) {
        for (int i = 0; i < res0.size(); i++) {
            if (res0.get(i).val == target.val) return i;
        }
        return -1;
    }

    void doDistanceK(int i, int K) {
        // 处理target下面节点
        down(i, K);
        up(i, K);

    }

    /**
     * 父节点记录错误
     *
     * @param i
     * @param K
     */
    void up(int i, int K) {
        TreeNode target = res0.get(i);
        if (K == 0) {
            distance.add(target.val);
            return;
        }
        if (res0.get(i - 1).left == target) {
            doDistanceK(i - 1, K - 1);

        } else {
            doDistanceK(i - 2, K - 1);
        }
    }

    void down(int i, int K) {
        if (!fonf.add(i)) return;
        TreeNode target = res0.get(i);
        if (K == 0) {
            distance.add(target.val);
            return;
        }
        if (target.left != null) down(i + 1, K - 1);
        if (target.right != null) down(i + 2, K - 1);
    }

    /**
     * 863. 二叉树中所有距离为 K 的结点 太---难了
     * <p>
     * 分治思想
     * <p>
     * 边界条件 root == target， 返回距离 k；
     * 若 root->left == target，则 left = k。 若 k == 1, 在左边找到目标，Push root->val；否则， k太长需要在右边找，solve(root->right, k - 2)，返回和当前root的距离 k - 1；
     * 若 root->right == target，则 right = k。 若 k == 1， 在左边找到目标，Push root->val；否则，k太长需要在左边找，sovle(root->left, k - 2)，返回和当前root的距离 k - 1.
     */
    List<Integer> res = new ArrayList<>();
    int k;

    public List<Integer> distanceKOfficial(TreeNode root, TreeNode target, int K) {
        k = K;
        dfs(root, target);
        return res;

    }

    public void getKFromRoot(TreeNode root, int k) {
        if (root == null) return;
        if (k == 0) res.add(root.val);
        getKFromRoot(root.left, k - 1);
        getKFromRoot(root.right, k - 1);
    }

    public int dfs(TreeNode root, TreeNode target) {
        if (root == null) return -1;
        if (root.val == target.val) {
            // 1、寻找子树节点
            getKFromRoot(root, k);
            return k;
        }
        // 这一步的作用？
        int l = dfs(root.left, target);
        int r = dfs(root.right, target);

        if (l < 0 && r < 0) {
            return -1;
        } else if (l > 0) {
            // 距离为1时，直接将父节点加入
            if (l == 1) res.add(root.val);
                // 父节点占用距离1,l-2
            else getKFromRoot(root.right, l - 2);
            // k 值-1
            return l - 1;
        } else {
            if (r == 1) res.add(root.val);
            else getKFromRoot(root.left, r - 2);
            return r - 1;
        }
    }
}
